package de.hsfulda.et.problemloesen.ws1112.grp2.knapsack;

import java.util.ArrayList;

public class CompleteEnumeration implements Optimizer {

    public Knapsack optimize(ArrayList<KnapsackItem> items,
	    ArrayList<Long> boundaryVector) {
	
	long solutionsCounter = 0L;
	long selection = 0;
	long weigthBoundary = boundaryVector.get(0);
	long maxCombinations = (long) Math.pow(2, items.size());
	boolean foundOne = false;
	int numItems =items.size();
	
	Knapsack kp = new Knapsack(items.size());
	
	for (selection = 0; selection < maxCombinations; selection++) {
	    long currentSum = 0;
	    long currentSelection = selection;
	    for (int j = 0; j < numItems; j++) {
		// is selected?
		long weight = items.get(j).getWeight();
		int selectedOrNot = (int) currentSelection%2;
		currentSum += (weight * selectedOrNot);
		// next item
		currentSelection = currentSelection >> 1;
	    	if (currentSelection == 0) break;
	    }
	    // is solution?
	    if (currentSum == weigthBoundary)
	    {
		// found a solution
		if (!foundOne) 
		{
		    // pack one knapsack, if it is first solution
		    long current = selection;
		    for (int k = 0; k < numItems; k++)
		    {
			if (current%2 == 1)
			{
			    kp.packIn(items.get(k), k);
			}
			current = current >> 1;
		    }
		    foundOne = true;
		}
		solutionsCounter++;
		System.out.println("Solution Nr: " + solutionsCounter + " - " + 
			100*((((double) selection) / ((double)maxCombinations))) + "%"); 
	    }
	}
	
	return kp;
    }
}
